package com.lw.leetcode.sort.b;

/**912. 排序数组
 * @Author liw
 * @Date 2021/6/30 17:15
 * @Version 1.0
 */
public class SortArray {


    private int[] item;
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }
        int length = nums.length;
        item = new int[length];
        find(nums, 0, length - 1);
        return nums;
    }

    private void find(int[] nums, int st, int end) {
        if (st >= end) {
            return;
        }
        int m = st + ((end - st) >> 1);
        find(nums, st, m);
        find(nums, m + 1, end);
        int i = st;
        int j = m + 1;
        int index = 0;
        while (i <= m && j <= end) {
            if (nums[i] > nums[j]) {
                item[index++] = nums[j++];
            } else {
                item[index++] = nums[i++];
            }
        }
        while (i <= m) {
            item[index++] = nums[i++];
        }
        while (j <= end) {
            item[index++] = nums[j++];
        }
        index = 0;
        for (int k = st; k <= end; k++) {
            nums[k] = item[index++];
        }
    }

}
